#include "heap.h"
#include <iostream>
using namespace std;

/*上浮*/
void Heap::floatUp()
{
    /*索引*/
    int index = m_container.getsize() - 1;
    while (index > 0)
    {
        /*父节点的索引 */
        int parentIndex = (index - 1) >> 1;
        if (m_container[index] >= m_container[parentIndex])
        {
            break;
        }
        /*程序到这个地方,就意味着当前索引的值比我父节点索引的值要小*/
        int tmp = m_container[index];
        m_container[index] = m_container[parentIndex];
        m_container[parentIndex] = tmp;

        /*更新index的值*/
        index = parentIndex;
    }
}

Heap::Heap() : m_container(10)
{
}

Heap::~Heap()
{
}

/*插入数据*/
void Heap::insertData(ElementType data)
{
    // m_container[m_container.getsize()] = data;
    // m_container.setSizeInc();

    // 直接插到数组的末尾
    m_container.InsertTail(data);
    /*满足堆的特性*/
    /*上浮*/
    floatUp();
    return;
}

/*获取堆顶元素*/
ElementType Heap::getHeapTop()
{

    if (m_container.getsize() == 0)
    {
        cout << "empty..."<< endl;
        return -1;
    }

    return m_container[0];
}

/*下滤*/
void Heap::sinkDown()
{
    int index = 0;
    int halfIndex = m_container.getsize() >> 1;
    while (index < halfIndex)
    {
        /*左子节点的索引 */
        int leftChildIndex = (index << 1) + 1;
        /*右子节点的索引 */
        int rightchildIndex = leftChildIndex + 1;
        int childIndex = leftChildIndex;
        if (rightchildIndex <= m_container.getsize() && m_container[leftChildIndex] > m_container[rightchildIndex])
        {
            childIndex = rightchildIndex;
        }
        /*当前的根和左节点和右节点比较 谁更小?*/
        if (m_container[index] < m_container[childIndex])
        {
            break;
        }
        /*交换*/
        ElementType tmp = m_container[index];
        m_container[index] = m_container[childIndex];
        m_container[childIndex] = tmp;
        index = childIndex;
    }
}

/*删除元素*/
void Heap::deleteData()
{
    int size = m_container.getsize();
    if (size == 0)
    {
        return;
    }

    /*将最后一个元素的值覆盖掉堆顶元素*/
    m_container[0] = m_container[size - 1];
    m_container.setSizeDec();
    sinkDown();
}
